קטגוריה: תורת הסיבוכיות

66 פוסטים

• 2020-01-24

  מה זה אומר ש-MIP*=RE? (חלק ב': מה זה אומר MIP*?)

• 2020-01-23

  מה זה אומר ש-MIP*=RE? (חלק א': מה זה אומר RE?)

• 2018-11-07

  ”הוכחה ראשונה לעליונות מחשב קוונטי“ - מה כן (אזהרה - עלול לכלול מתמטיקה)

• 2018-10-23

  ”הוכחה ראשונה לעליונות מחשב קוונטי“ - מה לא (וקצת מה כן)

• 2017-09-04

  על הבעיה הקשה של מלכות השחמט והבעיה הקשה עוד יותר של מלקות התקשורת

• 2016-07-12

  ההוכחה הארוכה ביותר בהיסטוריה! (או: איך פותרי SAT מתגברים על בעיות קומבינטוריות, אבל היי זה שם פחות מפוצץ)

• 2015-07-23

  משפט קוק-לוין

• 2015-05-28

  משפט קלייני - הוכחה נוספת

• 2015-05-14

  למת הניפוח לשפות רגולריות - גרסה מלאה

• 2015-05-07

  משפט מייהיל-נרוד - נקודת מבט נוספת, ואלגוריתמי מינימיזציה

• 2015-04-29

  בעיות הכרעה עבור שפות פורמליות

• 2015-04-26

  שפות חסרות הקשר - תכונות סגור

• 2015-04-15

  שפות חסרות הקשר - למת הניפוח, הלמה של אוגדן ושפות רב משמעיות

• 2015-03-31

  שקילות אוטומט מחסנית ודקדוק חסר הקשר

• 2015-03-22

  אוטומט מחסנית

• 2015-03-15

  אז מה הקשר בין דקדוקים חסרי הקשר ופונקציות יוצרות?

• 2015-03-05

  מבוא לדקדוקים חסרי הקשר

• 2015-02-11

  משפט מייהיל-נרוד

• 2015-02-03

  למת הניפוח לשפות רגולריות

• 2015-01-29

  ביטויים רגולריים

• 2014-12-24

  שפות רגולריות - משפט קלייני

• 2014-12-21

  שפות רגולריות - תכונות סגור (חלק ב')

• 2014-12-15

  שפות רגולריות - תכונות סגור (חלק א')

• 2014-11-19

  אוטומטים אי דטרמיניסטיים ושאר מריעין בישין

• 2014-11-11

  אוטומטים ושפות רגולריות - מבוא

• 2013-12-11

  פותרים את SAT - אלגוריתם DPLL

• 2013-11-24

  פותרים את SAT: המקרים של HORNSAT ו-2SAT

• 2013-11-14

  רזולוציה - איך אפשר להוכיח שאי אפשר?

• 2013-11-11

  מה זו בעיית SAT ולמה חשוב לפתור אותה?

• 2013-06-30

  על P=NP מעל חבורות אבליות - סוף דבר

• 2013-06-15

  על P=NP מעל חבורות אבליות - מבוא שלם

• 2012-05-11

  משפט Valiant-Vazirani, או: איך להרוג השמות מספקות עם פונקציות תמצות אקראיות

• 2011-05-14

  IP=PSPACE - ההוכחה (חלק ב')

• 2011-05-07

  IP=PSPACE - ההוכחה (חלק א')

• 2011-04-04

  אז מהי PSPACE?

• 2011-03-25

  מערכות הוכחה אינטראקטיביות - דוגמאות

• 2011-03-17

  אז מה זה IP=PSPACE?

• 2011-03-05

  NL=coNL ("משפט אימרמן") - מי, מה, כמה ולמה

• 2011-03-01

  מה זו סיבוכיות תקשורת?

• 2011-01-24

  משפט ברינגטון - ההוכחה

• 2011-01-23

  תוכניות מתפצלות ומשפט ברינגטון

• 2011-01-18

  מעגלים בוליאניים - מה זה בכלל?

• 2011-01-09

  פרוייקט "תוצאות מפתיעות בסיבוכיות" יוצא לדרך!

• 2010-11-10

  משפט לדנר, או - מפרקים לגורמים את NP

• 2010-08-31

  כיצד אורקלים מנבאים שקשה להוכיח ש-P שונה מ-NP

• 2010-08-16

  אז מדוע קשה להוכיח ש-P שונה מ-NP? (בלכסון)

• 2010-08-15

  אז מה זה עניין P=NP, בעצם?

• 2010-08-10

  הוכחה ש-P שונה מ-NP?

• 2009-10-04

  למה זכרון שהוא פחות מלגלג הוא קבוע?

• 2009-10-01

  אז מה בין קודים לתיקון שגיאות והוכחת משפט ה-PCP?

• 2009-09-23

  קודים לתיקון שגיאות (שניתנים לבדיקה מקומית)

• 2009-09-19

  משפט ה-PCP או: איך למדתי להפסיק לדאוג ולאהוב הוכחות הניתנות לבדיקה הסתברותית

• 2009-08-30

  אוטומטים סופיים ושפות רגולריות

• 2009-08-18

  דיון מקרי על אלגוריתמים הסתברותיים

• 2009-07-22

  למה RSA טרם נפרץ? (בגלל החשיבה המתמטית הלא פרקטית)

• 2008-01-07

  על בעיות שהן בכלל תסבוכת שלמה

• 2007-12-23

  אז מה זה בעצם אי דטרמיניזם? קשה להחליט

• 2007-12-16

  על הבעיה המסובכת של מציאת מחט בערימת שחת

• 2007-12-11

  מכונת טיורינג, 2: הנקמה (המסובכת)

• 2007-12-05

  למה גם מה שפתיר לא פתיר (זה מסובך)

• 2007-11-10

  אוף, כל הקטע עם השורש הריבועי באמת יוצא מסובך

• 2007-11-05

  ועכשיו למשהו מסובך יותר - הוצאת שורש ריבועי!

• 2007-09-07

  המגדל הלוהט

• 2007-07-25

  על משת”פים ונבוטים בראש, והקשר שלהם להוכחות אפס-ידע

• 2007-07-17

  עימות המוכיחים

• 2007-07-10

  מוכיח בשער

← חזרה לכל הקטגוריות